package SubjectTree.Four;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class GetMinimumDifference {

/**
 * 难度：简单
 * 
 * 530. 二叉搜索树的最小绝对差
 * 	给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
 * 	
 * 示例：
 * 	输入：
 * 	   1
 * 	    \
 * 	     3
 * 	    /
 * 	   2
 * 	输出：
 * 	1
 * 	解释：
 * 	最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
 * 	
 * 提示：
 * 	树中至少有 2 个节点。
 * 	本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		GetMinimumDifference gmd = new GetMinimumDifference();
		System.out.println(gmd.getMinimumDifference(TreeNode.MkTree("[1,null,3,null,null,2,null]")));
	}
	//自己写(中序遍历)
	public int getMinimumDifference(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode pre = null;
		int minValue = Integer.MAX_VALUE;
		while(!deque.isEmpty() || root!=null) {
			while(root!=null) {
				deque.push(root);
				root = root.left;
			}
			root = deque.pop();
			if(pre!=null) {
				minValue = Math.min(minValue, root.val - pre.val);
			}
			pre = root;//保存前一个访问的结点
			
			root = root.right;
		}
		return minValue;
    }
	//自己写(递归)
	int minValue = Integer.MAX_VALUE;
	TreeNode preNode = null;
	public int getMinimumDifference_1(TreeNode root) {
		if(root==null)return 0;
		getMinimumDifference_1(root.left); //左
		
		if(preNode!=null)minValue = Math.min(minValue, root.val - preNode.val);	//中
		preNode = root;
		
		getMinimumDifference_1(root.right);	//右
		return minValue;
    }
	
	//方法一：中序遍历
	int pre;
    int ans;
    public int getMinimumDifference1(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;	
    }
    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}
